/*
 * @Descripttion: 
 * @version: 
 * @Author: lily
 * @Date: 2021-04-28 09:47:30
 * @LastEditors: lily
 * @LastEditTime: 2021-04-28 10:08:16
 */
/*
 * @lc app=leetcode.cn id=64 lang=javascript
 *
 * [64] 最小路径和
 */

// @lc code=start
/**
 * @param {number[][]} grid
 * @return {number}
 */

//  思想：动态规划，同62
//  dp[m][n]表示最小数字 = 左和上的较小值 + 本格数字
//  状态转移方程:  dp[m][n] = min(dp[m-1][n], dp[m][n-1]) + grid[m][n]

//  复杂度：O(mn) O(mn)

var minPathSum = function (grid) {
    const m = grid.length, n = grid[0].length
    let dp = Array.from(new Array(m), () => new Array(n).fill(0))
    dp[0][0] = grid[0][0]
    // 设置初始值
    for (let i = 1; i < m; i++) {
        dp[i][0] = dp[i - 1][0] + grid[i][0]
    }
    for (let j = 1; j < n; j++) {
        dp[0][j] = dp[0][j - 1] + grid[0][j]
    }
    // 填表
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
        }
    }

    return dp[m - 1][n - 1]
};
// @lc code=end

console.log(minPathSum([[1, 2, 3], [4, 5, 6]]));